//
// GPSMapEdit
// (c) Konstantin Galichsky (kg@geopainting.com), 2002-2007
//
// Search of duplicated objects.
//

# include "StdAfx.h"
# include "Resource.h"
# include "RemoveDuplicates.h"
# include "Map.h"
# include "DeleteObject.h"
# include "DeleteElement.h"
# include "CombinedAction.h"
# include "Status.h"
# include "MapView.h"
# include "Globals.h"

struct re_t {
	rgn_t * pRgn;
	size_t  cElementOrOrigin;
};

void RemoveDuplicates (bool _bSilent) {
	size_t cDeletedElements = 0;
	size_t cDeletedRgns = 0;

	const int iDepth = BeginCombinedAction ();

	{
		CCritSec::CLock lock (g_cs);

		const size_t cTotalRgns = g_map.GetRgnCount ();
		if (cTotalRgns == 0)
			return;
		size_t cRgnsProcessed = 0;

		SetStatus (GetStr (IDS_STATUS_REMOVING));
		SetProgressStatus (0);

		for (size_t cKind = 0; cKind < rkMax; ++ cKind) {
			rgns_t & rgns = g_map.layers [cKind].rgns;

			//
			// Prepare matches.
			//

			typedef std::multimap<float, re_t> mapRE_t;
			mapRE_t mapRE;

			for (rgns_t::iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
				rgn_t & rgn = * iRgn;
				if (rgn.IsDeleted () || rgn.IsWTR ())
					continue;

				// Elements.
				const size_t cElements = rgn.elements.size ();
				for (size_t cElement = 0; cElement < cElements; ++ cElement) {
					rgn_element_t & element = rgn.elements [cElement];
					if (element.bDeleted)
						continue;

					const points_t & points = element.points;
					if (points.empty ())
						continue;

					const float fKey = points [0].x;

					const mapRE_t::iterator i = mapRE.insert (mapRE_t::value_type (fKey, re_t ()));
					re_t & re = i->second;
					re.pRgn = & rgn;
					re.cElementOrOrigin = cElement;
				}

				// Origins.
				const size_t cOrigins = rgn.origins.size ();
				for (size_t cOrigin = 0; cOrigin < cOrigins; ++ cOrigin) {
					rgn_origin_t & origin = rgn.origins [cOrigin];
					if (origin.bDeleted)
						continue;

					const float fKey = origin.point.x;

					const mapRE_t::iterator i = mapRE.insert (mapRE_t::value_type (fKey, re_t ()));
					re_t & re = i->second;
					re.pRgn = & rgn;
					re.cElementOrOrigin = cOrigin;
				}

				++ cRgnsProcessed;
				SetProgressStatus (cRgnsProcessed*100/cTotalRgns);
			}

			const bool bElements = cKind == rkPolygon || cKind == rkPolyline;

			//
			// Analyze the matches.
			//

			for (mapRE_t::iterator ib = mapRE.begin (); ib != mapRE.end ();) {
				const float fKey = ib->first;

				// Search for the end of equal range.
				mapRE_t::iterator ie = ib;
				++ ie;
				while (ie != mapRE.end () && ie->first == fKey)
					++ ie;

				// Analyse the equal range.
				for (mapRE_t::iterator i1 = ib; i1 != ie; ++ i1) {
					re_t & re1 = i1->second;

					rgn_element_t * const pElement1 = bElements ? & re1.pRgn->elements [re1.cElementOrOrigin] : NULL;
					rgn_origin_t  * const pOrigin1  = bElements ? NULL : & re1.pRgn->origins [re1.cElementOrOrigin];

					for (mapRE_t::iterator i2 = i1; i2 != ie; ++ i2) {
						if (i1 == i2)
							continue;

						re_t & re2 = i2->second;
						if (re2.pRgn->IsDeleted ())
							continue;

						// Compare whole objects.
						if (
							re1.pRgn != re2.pRgn &&
							re1.pRgn->ushType  == re2.pRgn->ushType &&
							re1.pRgn->strLabel == re2.pRgn->strLabel &&
							re1.pRgn->elements == re2.pRgn->elements &&
							re1.pRgn->origins  == re2.pRgn->origins
						) {
							++ cDeletedRgns;
							DeleteObject (re2.pRgn);
							continue;
						}

						// Compare elements of the objects.
						if (
							re1.pRgn->ushType != re2.pRgn->ushType ||
							! (re1.pRgn->strLabel == re2.pRgn->strLabel)
						)
							continue;

						rgn_element_t * const pElement2 = bElements ? & re2.pRgn->elements [re2.cElementOrOrigin] : NULL;
						rgn_origin_t  * const pOrigin2  = bElements ? NULL : & re2.pRgn->origins [re2.cElementOrOrigin];

						if (bElements ? pElement2->bDeleted : pOrigin2->bDeleted)
							continue;

						const bool bMatch = bElements ? * pElement1 == * pElement2 : * pOrigin1 == * pOrigin2;
						if (bMatch) {
							++ cDeletedElements;
							DeleteElement (re2.pRgn, re2.cElementOrOrigin);
						}
					}
				}

				ib = ie;
			}
		}
	}

	EndCombinedAction (iDepth, "remove duplicates");

	SetStatusReady ();
	Refresh ();

	if (! _bSilent) {
		WarningMsgBox (
			"The number of deleted\n"
			"  objects = %d\n"
			"  elements = %d.",
			cDeletedRgns, cDeletedElements
		);
	}
}
